/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/letter-combinations-of-a-phone-number
   @Language: C++
   @Datetime: 17-03-16 15:56
   */

// Method 1 recursion
class Solution {
	void getletter(string &digits,const vector<string> &alphas
			,int pos,vector<string> &vs,string &s){
		if (s.length()==digits.length()){
			vs.push_back(s);
			return;
		}
		for(int i=pos; i<digits.length(); ++i){
			const string &str = alphas[digits[i]-'0'];
			for(int j=0; j<str.length(); ++j){
				s.push_back(str[j]);
				getletter(digits,alphas,i+1,vs,s);
				s.pop_back();
			}
		}
	}

public:
	/**
	 * @param digits A digital string
	 * @return all posible letter combinations
	 * Tip: Do not need dictionary order
	 */
	vector<string> letterCombinations(string& digits) {
		// Write your code here
		if (digits.length()<1) return {};
		const vector<string> alphas={" ","","abc","def","ghi"
			,"jkl","mno","pqrs","tuv","wxyz"};
		vector<string> vs;
		string s;
		getletter(digits,alphas,0,vs,s);
		return vs;
	}
};

// Method 2 loop
class Solution {
public:
	/**
	 * @param digits A digital string
	 * @return all posible letter combinations
	 * Tip: Do not need dictionary order
	 */
	vector<string> letterCombinations(string& digits) {
		// Write your code here
		if (digits.length()<1) return {};
		const vector<string> alphas={" ","","abc","def","ghi"
			,"jkl","mno","pqrs","tuv","wxyz"};
		vector<string> vs = {""};
		for (int i=0; i<digits.length(); ++i){
			const string &str = alphas[digits[i]-'0'];
			if (str.length()<1) continue;
			const int size = vs.size();
			for (int j=0; j<size; vs[j++].push_back(str[0])){
				for (int k=1; k<str.length(); ++k){
					vs.push_back(vs[j]);
					vs.back().push_back(str[k]);
				}
			}
		}
		return vs;
	}
};
